#ifndef __BINARY_SEARCH_TREE_H__
#define __BINARY_SEARCH_TREE_H__

#define ELEMENTTYPE void *

typedef struct BalanceBinarySearchTreeNode
{
    /* 数据域 */
    ELEMENTTYPE  *data;

    /* 指针域 */
    struct BalanceBinarySearchTreeNode *left;
    struct BalanceBinarySearchTreeNode *right;
#if 1
    struct BalanceBinarySearchTreeNode * parent;//父结点
#endif

    /* 结点的高度 */
   int height;

}BalanceBinarySearchTreeNode;

typedef struct BalanceBinarySearchTree
{
    /* 树元素个数 */
    int size;
    /* 树的高度 */
    int height;
    /* 根节点 */
    BalanceBinarySearchTreeNode *root;//拿到根结点才能拿到树

    /* 自定义打印器 */
    int (*printFunc)(ELEMENTTYPE arg);

    /* 自定义比较器 */
    int (*compareFunc)(ELEMENTTYPE arg1, ELEMENTTYPE arg2);
}BalanceBinarySearchTree;



// /* 树的初始化 */
// int bnarySearchTreeInit(BalanceBinarySearchTree **pTree);

/* 树的初始化 */
int BalanceBinarySearchTreeInit(BalanceBinarySearchTree **pTree,  int (*compareFunc)(ELEMENTTYPE arg1, ELEMENTTYPE arg2), int (*printFunc)(ELEMENTTYPE arg));

/* 树的插入  */
int BalanceBinarySearchTreeInsert(BalanceBinarySearchTree *pTree, ELEMENTTYPE data);

/* 树的前序遍历 */
int BalanceBinarySearchTreePreOrder(BalanceBinarySearchTree *pTree);

/* 树的中序遍历 */
int BalanceBinarySearchTreeInOrder(BalanceBinarySearchTree *pTree);

/* 树的后序遍历 */
int BalanceBinarySearchTreePosOrder(BalanceBinarySearchTree *pTree);

/* 树的层序遍历 */
int bnarySearchTreeLeveOrder(BalanceBinarySearchTree *pTree);

/* 树的高度 */
int BalanceBinarySearchTreeGetHeight(BalanceBinarySearchTree *pTree, int *pHeight);

/* 销毁*/
int bnarySearchTreeDestroy(BalanceBinarySearchTree *pTree);

/* 树的删除 */
int BalanceBinarySearchTreeDelete(BalanceBinarySearchTree *pTree, ELEMENTTYPE data);

/* 树是否存在该元素值 */
int BalanceBinarySearchTreeIsContainVa(BalanceBinarySearchTree *pTree, ELEMENTTYPE data);


//获取树的元素个数
int BalanceBinarySearchTreeGetSize(BalanceBinarySearchTree *pTree, int *pSize);

#endif
